import java.util.*;
//贪心算法解决的0-1背包问题
class Obj{//用对象来存储每个物品的重量和价值
    int price;//price
    int weight;//weight
    double pw;//price/weight
    boolean mark=false;//标记位，表示是否被选中，本题中未使用，但很多类似的题中需要，加上供扩展算法
}
public class Greedy {
    public static double maxPrice(int cap,int num,int [][] objs){
        Obj[] objArr=new Obj[num];//创建物品对象
        for(int i=0;i<num;i++){
            objArr[i]=new Obj();
        }

        for(int i=0;i<num;i++){
            objArr[i].weight=objs[i][0];
            objArr[i].price=objs[i][1];
            objArr[i].pw=objs[i][1]*1.0/objs[i][0];
        }
        Arrays.sort(objArr,new Comparator<Obj>(){//重载Java数组自带排序方法，使用归并排序，方便而且排序效率高
            public int compare(Obj o1,Obj o2){
                if(o1.pw<o2.pw){
                    return 1;
                }
                else if(o1.pw==o2.pw){
                    return 0;
                }
                else
                    return -1;
            }
        });
        //总price与指示变量
        double pSum=0;
        int	i=0;
        while(cap>0){
            cap-=objArr[i].weight;
            pSum+=objArr[i].price;
            ;
            i++;
        }
        //若cap为负数，说明取多了，需要减去最后一个物品的一部分价值
        if(cap<=0){
            int gap=-cap;
            pSum-=gap*objArr[--i].pw;

        }
        return pSum;
    }

    public static void main(String[] args) {
        int cap=150;
        int num=7;
        int[][] objs={{35,10},{30,40},{60,30},{50,50},{40,35},{10,40},{25,30}};//创建二维数组用来初始化每个物品对象
        double maxP=maxPrice(cap, num, objs);
        System.out.println("最后放入背包的总价值为："+maxP);
    }
}
